METHOD OF RELIABLE CELLULAR CIRCUIT SYNTHESIS USING THE CHOICE FUNCTION

Rybakov Andrey Valentinovich, Postgraduate student, Penza State University (40 Krasnaya street, Penza, Russia), dm@pnzgu.ru

519.718

Background. One of the most important fileds of mathematical cybernetics is the theory of synthesis, reliability and complexity of control systems. Such models ofdiscrete functions computing as circuits made of functional gates are well known. These circuits, made of both absolutely reliable and unreliable gates, have been studied for a long time; there have been obtained multiple results. However, in real circuits it is necessary to take into account not just functioning of gates, but a circuit’s geometry as well. In this connection there has been suggested a model of cellular circuits made of functional gates, where the circuit is represented as a rectangle, divided into cells, containing circuit’s gates, having certain sizes and occupying a certain area. Cellular gates may be both functional, i.e. performing some function from their inputs, and switching ones, that transmit a signal to the next gate with a possible change of direction. The work presupposes that switching gates are absolutely reliable, and at any of two outputs of each functional gate at the same probability independently there occur inverse failures. Previously, there was suggested the method of building asymptotic reliability-optimal cellular circuits, based on expansion of a function by a variable. However, the circuits, built in such manner, are too complicated. The aim of the article is to signidicantly improve complexity estimation for asymptotically reliability-optimal cellular circuits.
Materials and methods. In order to build asymptotically reliability-optimal cellular circuits the author used cellular circuits realizing the choice functions. The article shows how to realize any Boolean function from n variables using such circuits, as well as estimates reliability and complexity of the suggested circuits, having a significantly lower complexity compared to the previously known.
Results. The author suggested the method of synthesis of asymptotically reliability- optimal cellular circuits with improved complexity. The researcher estimated reliability of the suggested circuits and proved the theorems of complexity thereof.
Conclusions. The known complexity estimation for asymptotically reliabilityoptimal cellular circuits has been significantly improved.

cellular circuits, functional and switching gates, synthesis and complexity of reliable cellular circuits.

1. Neuman von J. Automata studies . Princeton University Press, 1956.
2. Ortyukov S. I. Trudy seminara po diskretnoy matematike i ee prilozheniyam (Moskva, 27–29 yanvarya 1987 g.) [Proceedings of the seminar on discrete mathematics and application thereof (Moscow, 27-29 January 1987)]. Moscow: Izd-vo Mosk. un-ta, 1989, pp. 166–168.
3. Uhlig D. Fundamentals of Computation Theory. Intern. sonf. FCT'87 (Kazan, June 1987). Proc. Berlin: Springer-Verl., 1987, pp. 462–469.
4. Vasin A. V. Izvestiya vysshikh uchebnykh zavedeniy. Povolzhskiy region. Fizikomatematicheskie nauki [University proceedings. Volga region. Physical and mathematical sciences]. 2008, no. 4, pp. 2–16.
5. Alekhina M. A., Aksenov S. I. Diskretnaya matematika i ee prilozheniya: materialy IX Mezhdunar. seminara, posvyashch. 75-letiyu so dnya rozhdeniya O. B. Lupanova (Moskva, 18–23 iyunya 2007 g.) [Discrete mathematics and application thereof: proceedings of IX International seminar commemorating 75th jubilee of O.B. Lupanov (Moscow, 18-23 June 2007)]. Moscow: Izd-vo mekh.-mat. fak-ta MGU, 2007, pp. 56–59.
6. Kravtsov S. S. Problemy kibernetiki [Problems of cybernetics]. Issue 19. Moscow:Nauka,1967,pp.285–292.
7. Ulesova A. Yu. Slozhnost' realizatsii bulevykh funktsiy v nekotorykh modelyakh kletochnykh skhem: diplomnaya rabota [Complexity of Boolean functions realization in some models of cellular circuits: thesis work]. Moscow: MGU im. Lomonosova, fakul'tet VMiK, kafedra matematicheskoy kibernetiki, 2010, 25 p.
8. Alekhina M. A., Rybakov A. V. Izvestiya vysshikh uchebnykh zavedeniy. Fizikomatematicheskie nauki [University proceedings. Volga region. Physical and mathematical sciences]. 2014, no. 4 (32), pp. 5–16.
9. Red'kin N. P. Nadezhnost' i diagnostika skhem [Reliability and diagnostics of circuits]. Moscow: Izd-vo MGU, 1992, 192 p.